package 每日一题;

import java.util.List;

/**
 * 648. 单词替换
 * 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
 *
 * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
 *
 * 你需要输出替换之后的句子。
 *
 *
 *
 * 示例 1：
 *
 * 输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
 * 输出："the cat was rat by the bat"
 * 示例 2：
 *
 * 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
 * 输出："a a b c"
 *
 *
 * 提示：
 *
 * 1 <= dictionary.length <= 1000
 * 1 <= dictionary[i].length <= 100
 * dictionary[i] 仅由小写字母组成。
 * 1 <= sentence.length <= 10^6
 * sentence 仅由小写字母和空格组成。
 * sentence 中单词的总量在范围 [1, 1000] 内。
 * sentence 中每个单词的长度在范围 [1, 1000] 内。
 * sentence 中单词之间由一个空格隔开。
 * sentence 没有前导或尾随空格。
 *
 */
public class D220707_T0648 {
    Tree[] trees = new Tree[26];

    public String replaceWords(List<String> dictionary, String sentence) {
        //使用空格将单词分开
        String[] split = sentence.split(" ");

        //词根存入 字典树中
        for (String dword : dictionary) {
            saveWordIntoTrees(dword);
        }

        StringBuilder builder = new StringBuilder();

        //拼接词根或者 单词
        for (String word : split) {
            builder.append(getCiGen(word)).append(" ");
        }

        return builder.toString().trim();

    }

    //将词根存入字典树中
    public void saveWordIntoTrees(String word) {
        int length = word.length();
        Tree[] children = trees;
        int i = 0;
        for (; i < length - 1; i++) {
            if (children[word.charAt(i) - 'a'] != null) {
                children = children[word.charAt(i) - 'a'].children;
            } else {
                Tree tree = new Tree(word.charAt(i));
                children[word.charAt(i) - 'a'] = tree;
                children = tree.children;
            }

        }
        //最后一个字母
        if (children[word.charAt(i) - 'a'] == null) {
            children[word.charAt(i) - 'a'] = new Tree(word.charAt(i), true);
        } else {
            children[word.charAt(i) - 'a'].isEnd = true;
        }
    }

    // 查询是否存在词根 若有词根返回词根 没有词根返回原单词
    public String getCiGen(String word) {

        int length = word.length();

        String dictionary = "";
        Tree[] children = trees;
        for (int i = 0; i < length; i++) {
            char c = word.charAt(i);
            dictionary = dictionary + c;
            if (children[word.charAt(i) - 'a'] == null) {
                return word;
            } else if (children[word.charAt(i) - 'a'].isEnd) {
                return dictionary;
            }
            children = children[word.charAt(i) - 'a'].children;
        }
        return word;
    }


    //字典树
    class Tree {
        Character c;
        boolean isEnd;
        Tree[] children = new Tree[26];

        Tree(Character c) {
            this.c = c;
        }

        Tree(Character c, boolean isEnd) {
            this.c = c;
            this.isEnd = isEnd;
        }
    }
}
